fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define len(s) (int)s.size()
  4.  
  5. using namespace std;
  6. using ll = int64_t;
  7. using ld = long double;
  8. using pll = pair<ll, ll>;
  9. using pii = pair<int, int>;
  10.  
  11. const ll INF = 1e18;
  12.  
  13. const int MAXN = 1e5 + 11;
  14. int n, q, a[MAXN], b[MAXN];
  15. unordered_map<int, int> ids;
  16. vector<int> st[MAXN * 4];
  17.  
  18. void build(int id, int l, int r)
  19. {
  20.     if (l == r)
  21.     {
  22.         st[id].push_back(b[l]);
  23.     }
  24.     else
  25.     {
  26.         int mid = (l + r) >> 1;
  27.         build(id * 2, l, mid);
  28.         build(id * 2 + 1, mid + 1, r);
  29.  
  30.         merge(st[id * 2].begin(), st[id * 2].end(),
  31.               st[id * 2 + 1].begin(), st[id * 2 + 1].end(),
  32.               back_inserter(st[id]));
  33.     }
  34. }
  35.  
  36. int query(int id, int l, int r, int u, int v, int k)
  37. {
  38.     if (v < l || r < u)
  39.         return 0;
  40.     if (u <= l && r <= v)
  41.     {
  42.         return (st[id].size() - (upper_bound(st[id].begin(), st[id].end(), k) - st[id].begin()));
  43.     }
  44.  
  45.     int mid = (l + r) >> 1;
  46.     return query(id * 2, l, mid, u, v, k) + query(id * 2 + 1, mid + 1, r, u, v, k);
  47. }
  48.  
  49. int main()
  50. {
  51.     ios_base::sync_with_stdio(false);
  52.     cin.tie(NULL);
  53.     cout.tie(NULL);
  54.     // freopen("input.txt", "r", stdin);
  55.     // freopen("output.txt", "w", stdout);
  56.     cin >> n >> q;
  57.  
  58.     for (int i = 1; i <= n; ++i)
  59.     {
  60.         cin >> a[i];
  61.     }
  62.  
  63.     for (int i = n; i >= 1; --i)
  64.     {
  65.         if (ids.count(a[i]) == 0)
  66.             b[i] = 1e9;
  67.         else
  68.             b[i] = ids[a[i]];
  69.         ids[a[i]] = i;
  70.     }
  71.  
  72.     build(1, 1, n);
  73.  
  74.     while (q--)
  75.     {
  76.         int l, r;
  77.         cin >> l >> r;
  78.         cout << query(1, 1, n, l, r, r) << "\n";
  79.     }
  80. }
Success #stdin #stdout 0.01s 13404KB
comments (?)
stdin
copy 
5 3
1 1 2 1 3
1 5
2 4
3 5
stdout
copy 
3
2
3
https://ideone.com/WXCya2
language:
C++14 (gcc 8.3)
created:
16 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!